

// 从数组中找到前 K 个最大的元素，使用了一种高效的数据结构（最小堆）来实现。

import java.util.PriorityQueue;

/*
算法逻辑：
    用前 K 个元素初始化小根堆堆。
    遍历剩余元素（K+1开始），如果某个元素比堆顶大，就替换堆顶（保证堆中始终是当前最大的 K 个元素）。
    最后从堆中提取结果（注意：结果是从小到大排序的）

为什么用最小堆？
因为我们想快速访问当前 K 个元素中的 最小值。如果新元素比这个最小值大，就替换它，确保堆中始终是最大的 K 个元素。
* */
public class TopkProblem3 {
    //o(n*logK)
    public static int[] findKmax(int[] array,int k) {
        // 初始化最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        //O(K * logK)
        /*填充堆的前 K 个元素
        循环遍历数组的前 k 个元素（下标 0 到 k-1）。
        minHeap.offer(array[i])：将元素插入堆中，堆会自动调整结构（时间复杂度为 O(log K)）。
        此时堆的状态：堆中有 K 个元素，堆顶是这 K 个元素中的最小值。
       （例如 array = [5, 3, 9, 1, 7], k = 3，堆可能是 [1, 3, 9]，堆顶是 1）。
        * */
        for (int i = 0; i < k; i++) {
            minHeap.offer(array[i]);// 将数组前 K 个元素加入堆
        }


        //(n-k) * logK
        /*处理剩余元素
        从下标 k 开始遍历数组剩余元素（下标 k 到 array.length-1）。
        minHeap.peek()：获取堆顶元素（当前堆中的最小值，但不删除）。
        关键逻辑：
            如果当前元素 array[i] 大于 堆顶元素（top < array[i]），说明当前元素应该属于前 K 大元素。
            于是执行：
                minHeap.poll()：删除堆顶（移除当前最小值）。
                minHeap.offer(array[i])：将当前元素插入堆中（堆自动调整结构）。
        效果：堆的大小始终保持为 K，堆中始终存储当前已遍历元素中最大的 K 个值。
        （接上例：遍历到 7 时，堆顶是 1，1 < 7 成立 → 移除 1，插入 7，堆变为 [3, 7, 9]）。
        * */
        for (int i = k; i < array.length; i++) {
            int top = minHeap.peek(); // 查看堆顶元素（不删除）
            if (top < array[i]) {     // 如果当前元素 > 堆顶
                minHeap.poll();       // 移除堆顶（最小值）
                minHeap.offer(array[i]); // 插入当前元素
            }
        }

        /*提取结果
        创建一个大小为 K 的结果数组 ret。
        minHeap.poll()：每次弹出堆顶元素（最小堆的堆顶始终是当前最小值），并存入结果数组。
        注意结果顺序：
        由于最小堆的弹出顺序是 从小到大，结果数组 ret 实际上是 升序排列的前 K 大元素。
        接上例：堆 [3, 7, 9] 弹出顺序为 3 → 7 → 9，所以 ret = [3, 7, 9]，表示升序排列的前 3 大元素）。
        * */
        int[] ret = new int[k];         // 创建结果数组
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();    // 依次弹出堆中元素
        }
        return ret;
    }
}
